import java.util.LinkedList;
import java.util.List;

/**
 * @Author Fizz Pu
 * @Date 2020/9/28 下午9:02
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class Lee77 {
    List<List<Integer>> outer = new LinkedList<>();
    // 注意List接口没有removeLast(),removeFirst()方法，声明类型时，必须声明为LinkedList
    LinkedList<Integer> inner = new LinkedList<>();
    public List<List<Integer>> combine(int nums, int k) {
        if(nums <= 0 && k > nums)return null;
        int height = 1;
        dfs(nums, k, height);
        return  (List<List<Integer>>)outer;
    }


    void dfs(int nums, int k, int height){
        if(height > k){
            // 此处必须复制一份传入outer,否则后面回溯的时候内部元素发生改变
            outer.add(new LinkedList(inner));
        } else{
            // 遍历可行解, 使用visited数组来标记已经使用过的元素
            for(int i = height; i <= nums; ++i){
                    inner.add(i);
                    dfs(nums, k,height + 1); // 回溯到下一层
                    inner.removeLast();// 注意List接口没有removeLast(),removeFirst()方法，声明类型时，必须声明为LinkedList
                }
        }
    }
}
